#include <iostream>
#include <vector>
#include <unordered_map>
#include <cassert>

using namespace std;

// 454. 四数相加II
//给出四个整型数组A,B,C,D，寻找有多少i,j,k,l的组合，
// 使得A[i] + B[j] + C[k] + D[l] = 0。其中，A,B,C,D中均含有相同的元素个数N，且0 <= N <= 500。

/// Using Hash Map
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        assert(nums1.size() == nums2.size() && nums2.size() == nums3.size() && nums3.size() == nums4.size());

        unordered_map<int, int> record;
        // 初始化查找表
        for(int i = 0; i < nums3.size(); i++)
            for(int j = 0; j < nums4.size(); j++)
                record[nums3[i] + nums4[j]] ++;

        int res = 0;
        for(int i = 0; i < nums1.size(); i++)
            for(int j = 0; j < nums2.size(); j++)
                if(record.find(-nums1[i] - nums2[j]) != record.end())
                    res += record[-nums1[i] - nums2[j]];// 有多少个C[i]+D[j]

        return res;
    }
};

int main() {
    int a[] = {1, 2};
    int b[] = {-2, -1};
    int c[] = {-1, 2};
    int d[] = {0, 2};
    vector<int> a_vec = vector<int>(a, a + sizeof(a)/sizeof(int));
    vector<int> b_vec = vector<int>(b, b + sizeof(b)/sizeof(int));
    vector<int> c_vec = vector<int>(c, c + sizeof(c)/sizeof(int));
    vector<int> d_vec = vector<int>(d, d + sizeof(d)/sizeof(int));

    cout << Solution().fourSumCount(a_vec, b_vec, c_vec, d_vec) << endl; // a[0]+b[0]+c[0]+d[1] a[1]+b[1]+c[0]+d[0]
    return 0;
}
